import java.util.*;
import java.util.concurrent.ArrayBlockingQueue;

public class ImpossibleGame {
	private static final int[] vertexCount = {0, 4,10,20,35,56,84,120,165,220,286,364,455,560,680,816,969,1140,1330,1540,1771,2024,2300,2600,2925,3276,3654,4060,4495,4960,5456};

	private static class Vertex {
		private final int[] description;

		private Vertex(int[] description) {
			this.description = description;
		}

		@Override
		public boolean equals(Object o) {
			if (this == o) return true;
			if (o == null || getClass() != o.getClass()) return false;

			Vertex vertex = (Vertex) o;

			return Arrays.equals(description, vertex.description);

		}

		@Override
		public int hashCode() {
			return description != null ? Arrays.hashCode(description) : 0;
		}
	}

	public long getMinimum(int k, String[] before, String[] after) {
		long[][] C = new long[k + 1][k + 1];
		for (int i = 0; i <= k; i++) {
			C[i][0] = 1;
			for (int j = 1; j <= i; j++)
				C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
		}
		int[][] vertices = new int[vertexCount[k]][];
		int index = 0;
		for (int a = 0; a <= k; a++) {
			for (int b = 0; a + b <= k; b++) {
				for (int c = 0; a + b + c <= k; c++) {
					int d = k - a - b - c;
					vertices[index++] = new int[]{a, b, c, d};
				}
			}
		}
		int[][] beforeCount = new int[before.length][4];
		int[][] afterCount = new int[after.length][4];
		for (int i = 0; i < before.length; i++) {
			for (int j = 0; j < before[i].length(); j++) {
				beforeCount[i][before[i].charAt(j) - 'A']++;
				afterCount[i][after[i].charAt(j) - 'A']++;
			}
		}
		Graph graph = new SparseGraph(vertexCount[k]);
		Map<Vertex, Integer> vertexIndex = new HashMap<Vertex, Integer>();
		for (int i = 0; i < vertexCount[k]; i++)
			vertexIndex.put(new Vertex(vertices[i]), i);
		for (int i = 0; i < vertexCount[k]; i++) {
			for (int j = 0; j < before.length; j++) {
				boolean good = true;
				for (int l = 0; good && l < 4; l++) {
					if (vertices[i][l] < beforeCount[j][l])
						good = false;
				}
				if (good) {
					int[] to = new int[4];
					System.arraycopy(vertices[i], 0, to, 0, 4);
					for (int l = 0; l < 4; l++)
						to[l] += afterCount[j][l] - beforeCount[j][l];
					graph.addEdge(new SimpleEdge(i, vertexIndex.get(new Vertex(to))));
				}
			}
		}
		int[] colors = strongComponents(graph);
		long[] vertexWeight = new long[vertexCount[k]];
		for (int i = 0; i < vertexCount[k]; i++) {
			int sum = k;
			vertexWeight[i] = 1;
			for (int j = 0; j < 4; j++) {
				vertexWeight[i] *= C[sum][sum - vertices[i][j]];
				sum -= vertices[i][j];
			}
		}
		int colorCount = 0;
		for (int color : colors)
			colorCount = Math.max(colorCount, color + 1);
		boolean[][] colorGraph = new boolean[colorCount][colorCount];
		List<Edge> edges = graph.getEdges();
		for (Edge edge : edges)
			colorGraph[colors[edge.getSource()]][colors[edge.getDestination()]] = true;
		long[] colorWeight = new long[colorCount];
		for (int i = 0; i < vertexCount[k]; i++)
			colorWeight[colors[i]] += vertexWeight[i];
		long bestResult = 0;
		long[] result = new long[colorCount];
		for (int i = colorCount - 1; i >= 0; i--) {
			result[i] = 0;
			for (int j = i + 1; j < colorCount; j++) {
				if (colorGraph[i][j])
					result[i] = Math.max(result[i], result[j]);
			}
			result[i] += colorWeight[i];
			bestResult = Math.max(bestResult, result[i]);
		}
		return bestResult;
	}

	public static int[] topologicalSort(Graph graph, boolean allowCycles) {
		final int[] order = new int[graph.getVertexCount()];
		final boolean[] onPath = new boolean[graph.getVertexCount()];
		final boolean[] hasCycle = new boolean[1];
		graph.fullDFS(new FullDFSCallbackAdapter<Object>() {
			private int index = 0;

			@Override
			public Object enterUnvisitedVertex(Graph graph, int vertex, Edge edge, Object o) {
				onPath[vertex] = true;
				return null;
			}

			@Override
			public Object enterVisitedVertex(Graph graph, int vertex, Edge edge, Object o) {
				if (edge == null)
					return null;
				if (onPath[edge.getDestination()])
					hasCycle[0] = true;
				return null;
			}

			@Override
			public void exitVertex(Graph graph, int vertex, Edge edge, Object o, Object currentResult) {
				order[index++] = vertex;
				onPath[vertex] = false;
			}
		});
		if (hasCycle[0] && !allowCycles)
			return null;
		return order;
	}

	private static class ComponentsCallback implements FullBFSCallback {
		private int componentNumber = -1;
		private final int[] components;

		public ComponentsCallback(int[] components) {
			this.components = components;
		}

		public void bfsStarted(Graph graph, int vertex) {
			components[vertex] = ++componentNumber;
		}

		public boolean vertexAdded(Graph graph, Edge edge) {
			components[edge.getDestination()] = componentNumber;
			return true;
		}

		public void alreadyVisited(Graph graph, Edge edge) {}

	}

	public static int[] strongComponents(Graph graph) {
		int[] topologicalOrder = topologicalSort(graph, true);
		reverseArray(topologicalOrder);
		Graph transposed = graph.transposed();
		final int[] components = new int[graph.getVertexCount()];
		transposed.fullBFS(new ComponentsCallback(components), topologicalOrder);
		return components;
	}

	public static void reverseArray(int[] array) {
		int lastIndex = array.length - 1;
		for (int i = array.length / 2 - 1; i != -1; i--) {
			int temp = array[i];
			array[i] = array[lastIndex - i];
			array[lastIndex - i] = temp;
		}
	}

	public interface DFSCallback<R, P> {
		public static final Object EMPTY_PARAMETERS = new Object();
		public R enterUnvisitedVertex(Graph graph, int vertex, Edge edge, P parameters);
		public R enterVisitedVertex(Graph graph, int vertex, Edge edge, P parameters);
		public void exitVertex(Graph graph, int vertex, Edge edge, P parameters, R currentResult);
		public P beforeUsingEdge(Graph graph, int vertex, Edge edge, P parameters, R currentResult, Edge nextEdge);
		public boolean afterVisitingEdge(Graph graph, int vertex, Edge edge, P parameters, R currentResult,
				Edge nextEdge, R visitResult, P passedParameters);
	}

	public static abstract class DFSCallbackAdapter<R> implements DFSCallback<R, Object> {
		public R enterUnvisitedVertex(Graph graph, int vertex, Edge edge, Object parameters) {
			return null;
		}

		public R enterVisitedVertex(Graph graph, int vertex, Edge edge, Object parameters) {
			return null;
		}

		public void exitVertex(Graph graph, int vertex, Edge edge, Object parameters, Object currentResult) {
		}

		public Object beforeUsingEdge(Graph graph, int vertex, Edge edge, Object parameters, Object currentResult,
								 Edge nextEdge) {
			return EMPTY_PARAMETERS;
		}

		public boolean afterVisitingEdge(Graph graph, int vertex, Edge edge, Object parameters, Object currentResult, Edge nextEdge,
										 Object visitResult, Object passedParameters)
		{
			return true;
		}
	}

	public interface FullDFSCallback<R, P> extends DFSCallback<R, P> {
		public R start(Graph graph);
		public P beforeEnteringVertex(R currentResult, int startVertex);
		public boolean afterEnteringVertex(R currentResult, int startVertex, R visitResult, P parameters);
		public void finish(Graph graph, R currentResult);
	}

	public static abstract class FullDFSCallbackAdapter<R> extends DFSCallbackAdapter<R>
			implements FullDFSCallback<R, Object>
	{
		public R start(Graph graph) {
			return null;
		}

		public Object beforeEnteringVertex(R currentResult, int startVertex) {
			return EMPTY_PARAMETERS;
		}

		public boolean afterEnteringVertex(R currentResult, int startVertex, R visitResult, Object parameters) {
			return true;
		}

		public void finish(Graph graph, R currentResult) {
		}
	}

	public interface BFSCallback {
		public boolean vertexAdded(Graph graph, Edge edge);
		public void alreadyVisited(Graph graph, Edge edge);
	}

	public interface FullBFSCallback extends BFSCallback {
		public void bfsStarted(Graph graph, int vertex);
	}

	public interface Edge {
		public int getSource();
		public int getDestination();

		public Edge getTransposedEdge();
	}

	public static class SimpleEdge implements Edge {
		protected final int source;
		protected final int destination;

		public SimpleEdge(int source, int destination) {
			this.source = source;
			this.destination = destination;
		}

		public int getSource() {
			return source;
		}

		public int getDestination() {
			return destination;
		}

		public Edge getTransposedEdge() {
			return new TransposedEdge(this);
		}
	}

	public static class TransposedEdge implements Edge {
		private final Edge parent;

		public TransposedEdge(Edge parent) {
			this.parent = parent;
		}

		public int getSource() {
			return parent.getDestination();
		}

		public int getDestination() {
			return parent.getSource();
		}

		public Edge getTransposedEdge() {
			return parent;
		}
	}

	public interface Graph {
		public int getVertexCount();
		public List<Edge> getIncident(int source);
		public void addEdge(Edge edge);

		public <R, P> R fullDFS(FullDFSCallback<R, P> callback);

		public void fullBFS(FullBFSCallback callback, int[] order);
		public List<Edge> getEdges();
		public Graph transposed();
	}

	public static class SparseGraph implements Graph {
		private final int vertexCount;
		private final List<Edge>[] edges;
		private List<Edge> allEdges = null;

		public SparseGraph(int vertexCount) {
			this.vertexCount = vertexCount;
			//noinspection unchecked
			edges = new List[vertexCount];
			for (int i = 0; i < vertexCount; i++)
				edges[i] = new ArrayList<Edge>();
		}

		public int getVertexCount() {
			return vertexCount;
		}

		public void addEdge(Edge edge) {
			allEdges = null;
			edges[edge.getSource()].add(edge);
		}

		public <R, P> R fullDFS(FullDFSCallback<R, P> callback) {
			boolean[] visited = new boolean[vertexCount];
			R result = callback.start(this);
			for (int i = 0; i < vertexCount; i++) {
				P parameters = callback.beforeEnteringVertex(result, i);
				if (parameters == null)
					continue;
				R currentResult = dfsImpl(i, callback, visited, parameters, null);
				if (!callback.afterEnteringVertex(result, i, currentResult, parameters))
					break;
			}
			callback.finish(this, result);
			return result;
		}

		private void bfsImpl(int startVertex, BFSCallback callback, boolean[] visited) {
			if (visited[startVertex])
				return;
			Queue<Integer> queue = new ArrayBlockingQueue<Integer>(vertexCount);
			queue.add(startVertex);
			visited[startVertex] = true;
			while (!queue.isEmpty()) {
				int currentVertex = queue.poll();
				for (Edge edge : getIncident(currentVertex)) {
					int destination = edge.getDestination();
					if (!visited[destination] && callback.vertexAdded(this, edge)) {
						visited[destination] = true;
						queue.add(destination);
					} else if (visited[destination])
						callback.alreadyVisited(this, edge);
				}
			}
		}

		public void fullBFS(FullBFSCallback callback, int[] order) {
			boolean[] visited = new boolean[vertexCount];
			for (int i : order) {
				if (!visited[i]) {
					callback.bfsStarted(this, i);
					bfsImpl(i, callback, visited);
				}
			}
		}

		public List<Edge> getEdges() {
			if (allEdges != null)
				return allEdges;
			allEdges = new ArrayList<Edge>();
			for (int i = 0; i < vertexCount; i++)
				allEdges.addAll(getIncident(i));
			return allEdges;
		}

		public Graph transposed() {
			Graph graph = new SparseGraph(vertexCount);
			for (Edge edge : getEdges())
				graph.addEdge(edge.getTransposedEdge());
			return graph;
		}

		private <R, P> R dfsImpl(int vertex, DFSCallback<R, P> callback, boolean[] visited, P parameters, Edge edge) {
			if (visited[vertex])
				return callback.enterVisitedVertex(this, vertex, edge, parameters);
			R result = callback.enterUnvisitedVertex(this, vertex, edge, parameters);
			visited[vertex] = true;
			for (Edge nextEdge : getIncident(vertex)) {
				P passedParameters = callback.beforeUsingEdge(this, vertex, edge, parameters, result,
						nextEdge);
				if (passedParameters == null) {
					if (!callback.afterVisitingEdge(this, vertex, edge, parameters, result, nextEdge, null, null))
						break;
					continue;
				}
				if (!callback.afterVisitingEdge(this, vertex, edge, parameters, result, nextEdge,
						dfsImpl(nextEdge.getDestination(), callback, visited, passedParameters, nextEdge),
						passedParameters))
				{
					break;
				}
			}
			callback.exitVertex(this, vertex, edge, parameters, result);
			return result;
		}

		public List<Edge> getIncident(int source) {
			return edges[source];
		}
	}

// BEGIN CUT HERE
	public static void main(String[] args) {
		if (args.length == 0) {
			ImpossibleGameHarness.run_test(-1);
		} else {
			for (String arg : args) ImpossibleGameHarness.run_test(Integer.valueOf(arg));
		}
	}
// END CUT HERE
}

// BEGIN CUT HERE
class ImpossibleGameHarness {
	public static void run_test(int casenum) {
		if (casenum != -1) {
			if (runTestCase(casenum) == -1)
				System.err.println("Illegal input! Test case " + casenum + " does not exist.");
			return;
		}
		
		int correct = 0, total = 0;
		for (int i=0;; ++i) {
			int x = runTestCase(i);
			if (x == -1) {
				if (i >= 100) break;
				continue;
			}
			correct += x;
			++total;
		}
		
		if (total == 0) {
			System.err.println("No test cases run.");
		} else if (correct < total) {
			System.err.println("Some cases FAILED (passed " + correct + " of " + total + ").");
		} else {
			System.err.println("All " + total + " tests passed!");
		}
	}
	
	static boolean compareOutput(long expected, long result) { return expected == result; }
	static String formatResult(long res) {
		return String.format("%d", res);
	}
	
	static int verifyCase(int casenum, long expected, long received) { 
		System.err.print("Example " + casenum + "... ");
		if (compareOutput(expected, received)) {
			System.err.println("PASSED");
			return 1;
		} else {
			System.err.println("FAILED");
			System.err.println("    Expected: " + formatResult(expected)); 
			System.err.println("    Received: " + formatResult(received)); 
			return 0;
		}
	}

	static int runTestCase(int casenum) {
		switch(casenum) {
		case 0: {
			int k                     = 1;
			String[] before           = { "A" } ;
			String[] after            = { "B" } ;
			long expected__           = 2L;

			return verifyCase(casenum, expected__, new ImpossibleGame().getMinimum(k, before, after));
		}
		case 1: {
			int k                     = 2;
			String[] before           = { "A", "A", "D" } ;
			String[] after            = { "B", "C", "D" } ;
			long expected__           = 5L;

			return verifyCase(casenum, expected__, new ImpossibleGame().getMinimum(k, before, after));
		}
		case 2: {
			int k                     = 2;
			String[] before           = { "B", "C", "D" } ;
			String[] after            = { "C", "D", "B" } ;
			long expected__           = 9L;

			return verifyCase(casenum, expected__, new ImpossibleGame().getMinimum(k, before, after));
		}
		case 3: {
			int k                     = 6;
			String[] before           = { "AABBC", "AAAADA", "AAACA", "CABAA", "AAAAAA", "BAAAA" } ;
			String[] after            = { "AACCB", "DAAABC", "AAAAD", "ABCBA", "AABAAA", "AACAA" } ;
			long expected__           = 499L;

			return verifyCase(casenum, expected__, new ImpossibleGame().getMinimum(k, before, after));
		}

		// custom cases

/*      case 4: {
			int k                     = ;
			String[] before           = ;
			String[] after            = ;
			long expected__           = L;

			return verifyCase(casenum, expected__, new ImpossibleGame().getMinimum(k, before, after));
		}*/
/*      case 5: {
			int k                     = ;
			String[] before           = ;
			String[] after            = ;
			long expected__           = L;

			return verifyCase(casenum, expected__, new ImpossibleGame().getMinimum(k, before, after));
		}*/
/*      case 6: {
			int k                     = ;
			String[] before           = ;
			String[] after            = ;
			long expected__           = L;

			return verifyCase(casenum, expected__, new ImpossibleGame().getMinimum(k, before, after));
		}*/
		default:
			return -1;
		}
	}
}

// END CUT HERE
